class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def findClosestLeaf(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        self.min_path = float('inf')
        self.min_node = None

        def search(node):
            if node.val == k:
                if node.left:
                    left_flag, left_count, left_node = search(node.left)
                    if node.right:
                        right_flag, right_count, right_node = search(node.right)
                        if left_count <= right_count:
                            now_node = left_node
                            now_dist = left_count + 1
                        else:
                            now_node = right_node
                            now_dist = right_count + 1
                        if now_dist < self.min_path:
                            self.min_path = now_dist
                            self.min_node = now_node
                        return True, 0, now_node
                    else:
                        now_node = left_node
                        now_dist = left_count + 1
                        if now_dist < self.min_path:
                            self.min_path = now_dist
                            self.min_node = now_node
                        return True, 0, now_node
                else:
                    if node.right:
                        right_flag, right_count, right_node = search(node.right)
                        now_node = right_node
                        now_dist = right_count + 1
                        if now_dist < self.min_path:
                            self.min_path = now_dist
                            self.min_node = now_node
                        return True, 0, now_node
                    else:
                        self.min_path = 0
                        self.min_node = node
                        return True, 0, node
            else:
                if node.left:
                    left_flag, left_count, left_node = search(node.left)
                    if node.right:
                        right_flag, right_count, right_node = search(node.right)
                        if left_flag:
                            now_node = right_node
                            now_dist = left_count + right_count + 2
                            if now_dist < self.min_path:
                                self.min_path = now_dist
                                self.min_node = now_node
                            return True, left_count + 1, None
                        if right_flag:
                            now_node = left_node
                            now_dist = left_count + right_count + 2
                            if now_dist < self.min_path:
                                self.min_path = now_dist
                                self.min_node = now_node
                            return True, right_count + 1, None
                        if left_count <= right_count:
                            now_node = left_node
                            now_dist = left_count + 1
                        else:
                            now_node = right_node
                            now_dist = right_count + 1
                        return False, now_dist, now_node
                    else:
                        return left_flag, left_count + 1, left_node
                else:
                    if node.right:
                        right_flag, right_count, right_node = search(node.right)
                        return right_flag, right_count + 1, right_node
                    else:
                        return False, 0, node
        search(root)
        return self.min_node.val






